{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降算法Demo\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实例: \n",
    "\n",
    "$$y = 3x_1 + 4x_2$$\n",
    "\n",
    "|$x_1$|$x_2$|$y$|\n",
    "|:---:|:---:|:---:|\n",
    "|1|4|19|\n",
    "|2|5|26|\n",
    "|5|1|19|\n",
    "|4|2|29|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参数函数: $h(\\theta_1, \\theta_2) = \\theta_1x_1 + \\theta_2x_2$\n",
    "\n",
    "损失函数: $J(\\theta) = \\dfrac{1}{2m} \\sum\\limits_{i=1}^m{\\big[ h(x^i) - y^i \\big]^2}$\n",
    "其中$\\dfrac{1}{2}$ 为了计算偏导数消除它"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "目标使得损失函数值最小, 求偏导:\n",
    "\n",
    "$\\dfrac{\\partial{J(\\theta)}}{\\partial{\\theta_j}} = \\dfrac{1}{m}\\sum\\limits_{i=1}^{m}\\big[h(x^i) - y^i \\big] x_j^i $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于是要最小化损失函数，所以参数θ按其负梯度方向来更新：\n",
    "\n",
    "$\\theta' = \\theta - \\alpha \\dfrac{\\partial{J(\\theta)}}{\\partial{\\theta_j}}$\n",
    "$\\alpha$是learning rate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 全局变量\n",
    "\n",
    "import random \n",
    "\n",
    "xs = [[1,4], [2,5], [5,1], [4,2]]\n",
    "ys = [19,26,19,20] \n",
    "\n",
    "eps = 0.0001  # 精度\n",
    "max_iters = 10000 \n",
    "step_size = 0.01 # learning rate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loss =  9.428456066652548e-05\n",
      "iter_count: 97\n",
      "y = 3.00*x1 + 4.00*x2\n"
     ]
    }
   ],
   "source": [
    "## BGD(Batch gradient descent)批量梯度下降法：每次迭代使用所有的样本\n",
    "\n",
    "# m = 4 (所有样本)\n",
    "def bgd():\n",
    "    iter_count = 0\n",
    "    theta = [1,1]\n",
    "    m = 4\n",
    "    while (True):\n",
    "        err1sum = 0\n",
    "        err2sum = 0\n",
    "        loss = 0\n",
    "        for i in range(4):\n",
    "            pred_y = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "            err1sum += (pred_y - ys[i]) * xs[i][0]\n",
    "            err2sum += (pred_y - ys[i]) * xs[i][1]\n",
    "        theta[0] = theta[0] - step_size * err1sum / m\n",
    "        theta[1] = theta[1] - step_size * err2sum / m\n",
    "        iter_count += 1\n",
    "        \n",
    "        # 损失函数\n",
    "        for i in range(4):\n",
    "            pred_y = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "            loss += (1/(2*m)) * (pred_y - ys[i])**2\n",
    "        if (loss < eps or iter_count > max_iters):\n",
    "            print(\"loss = \", loss)\n",
    "            break\n",
    "    print(\"iter_count:\", iter_count)\n",
    "    print(\"y = %.2f*x1 + %.2f*x2\" % (theta[0], theta[1]))\n",
    "    \n",
    "bgd()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loss =  9.603971783298928e-05\n",
      "iter_count: 99\n",
      "y = 3.00*x1 + 4.00*x2\n"
     ]
    }
   ],
   "source": [
    "## SGD（Stochastic gradientdescent）随机梯度下降法：每次迭代使用一组样本\n",
    "\n",
    "def sgd():\n",
    "    iter_count = 0\n",
    "    theta = [1,1]\n",
    "    m = 1\n",
    "    while (True):\n",
    "        loss = 0\n",
    "        i = random.randint(0, 3)\n",
    "        pred_y = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "        err1sum = (pred_y - ys[i]) * xs[i][0]\n",
    "        err2sum = (pred_y - ys[i]) * xs[i][1]\n",
    "        theta[0] = theta[0] - step_size * err1sum / m\n",
    "        theta[1] = theta[1] - step_size * err2sum / m\n",
    "        \n",
    "        iter_count += 1\n",
    "        \n",
    "        # 损失函数\n",
    "        for i in range(4):\n",
    "            pred_y = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "            loss += (1/(2*m)) * (pred_y - ys[i])**2\n",
    "        if (loss < eps or iter_count > max_iters):\n",
    "            print(\"loss = \", loss)\n",
    "            break\n",
    "    print(\"iter_count:\", iter_count)\n",
    "    print(\"y = %.2f*x1 + %.2f*x2\" % (theta[0], theta[1]))\n",
    "    \n",
    "sgd() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loss =  9.814308420142368e-05\n",
      "iter_count: 105\n",
      "y = 3.00*x1 + 4.00*x2\n"
     ]
    }
   ],
   "source": [
    "## MBGD（Mini-batch gradient descent）小批量梯度下降：每次迭代使用b组样本\n",
    "def mbgd():\n",
    "    iter_count = 0\n",
    "    theta = [1,1]\n",
    "    m = 2 # 取两个样本\n",
    "    while (True):\n",
    "        loss = 0\n",
    "        err1sum = 0\n",
    "        err2sum = 0\n",
    "        i = random.randint(0, 3)\n",
    "        j = (i + 1) % 4\n",
    "        pred_yi = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "        pred_yj = theta[0]*xs[j][0] + theta[1]*xs[j][1]\n",
    "        err1sum += (pred_yi - ys[i]) * xs[i][0]\n",
    "        err2sum += (pred_yi - ys[i]) * xs[i][1]\n",
    "        err1sum += (pred_yj - ys[j]) * xs[j][0]\n",
    "        err2sum += (pred_yj - ys[j]) * xs[j][1]\n",
    "        theta[0] = theta[0] - step_size * err1sum / m\n",
    "        theta[1] = theta[1] - step_size * err2sum / m\n",
    "        \n",
    "        iter_count += 1\n",
    "        \n",
    "        # 损失函数\n",
    "        for i in range(4):\n",
    "            pred_y = theta[0]*xs[i][0] + theta[1]*xs[i][1]\n",
    "            loss += (1/(2*m)) * (pred_y - ys[i])**2\n",
    "        if (loss < eps or iter_count > max_iters):\n",
    "            print(\"loss = \", loss)\n",
    "            break\n",
    "    print(\"iter_count:\", iter_count)\n",
    "    print(\"y = %.2f*x1 + %.2f*x2\" % (theta[0], theta[1]))\n",
    "    \n",
    "mbgd() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[更多参考](https://blog.csdn.net/kwame211/article/details/80364079)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
